Execution planning

実行計画

クエリプランナーとプロセッサーの初期の実装は、クライアントから提出された式ツリーのための式ツリーバインダーとコンパイラに過ぎませんでした。このコードは、キー／バリューストアのコプロックのコンテキストで実行され、クエリの対象となるデータと一緒に配置されていました。クエリが実行されている間、クエリを適切な場所にルーティングしたり、ノード間の通信を最適化したりするロジックはほとんどありません。むしろ、クエリによってタッチされたノードとエッジは、中間オブジェクトモデルを介して、基礎となるストアから取得されたキー／バリューのペア（およびそのコレクション）に対するインメモリコード実行を使用してクエリを実行していました。

The initial implementation of the query planner and processor was merely an expression tree binder and compiler for the expression trees submitted by clients. This code ran in the context of an key/value store coproc, collocated with the data being queried. Very little logic went into routing the query to the appropriate location or optimizing the communication across nodes while the query was being executed. Rather, the nodes and edges touched by the query were being queried using in-memory code execution on the key/value pairs (and collections thereof) retrieved from the underlying store, through an intermediate object model.

適切な実装に近づけるために、実行計画フェーズを導入するステップを踏みました。これにより、最終的には、原始的なグラフクエリ操作を異なるノードに送信して、より良いデータ局所性を得ることができます。さらに、実行可能なプランをランク付けするための様々な指標（RDBMSシステムにおける伝統的なヒストグラムを参照）を取り入れることで、クエリ式の静的な分析とそれに続く代数的な書き換えの適用を超えた最適化が可能になります。

In order to get closer to a proper implementation, steps were taken to introduce an execution planning phase, which would ultimately result in sending primitive graph query operations across different nodes to get better data locality. In addition, this would also enable optimizations that go beyond static analysis of the query expressions followed by application of algebraic rewrites, by incorporating various metrics to rank possible execution plans (cf. traditional histograms in RDBMS systems).

入力されたクエリ式と実行プランの間の変換は、Bottom Up Rewrite Systemの略である「BURS」と呼ばれるLINQ to Everythingユーティリティを使用して実装されました。これは、Todd Proebsting氏のBURSのバリエーションを、.NETの式木やオブジェクト指向言語でモデル化された他のAST用に実装したものです。Proebstin氏のオリジナルのBURSは、ASTを一連の命令に変換する最適化テーブル駆動型のコードジェネレータであり、すべてのルールがコストを指定することを意図していました。LINQ to Everythingツールキットの一部として書かれたBURSの実装は、これをさらに抽象化し、一般化されたツリー、ノード、タグの概念を使ってモデル化されたあらゆる言語のペアに対して、テーブル駆動型のコスト最適化変換を可能にしています。例えば、LINQ to SQLの実装では、まず、.NETの式木をボトムアップタイリングが可能な別の木表現に変換し、続いてターゲットのSQL言語を同様の木オブジェクトモデルを使用してモデリングします。最後に、ソース言語とデスティネーション言語の間で翻訳するために、コストに注釈を付けたルールのセットが宣言されます（例えば、Queryable.Selectに対するMethodCallExpressionは、SQLのProjectノードに翻訳され、それが後にSELECT句の構文に変換されます）。BURSの使用により、チームは比較的早くクエリプロセッサを構築することができました。

Translation between the incoming query expression and the execution plan was implemented using a LINQ to Everything utility called “BURS” which stands for Bottom Up Rewrite System. It’s an implementation of a variation of Todd Proebsting’s BURS for .NET expression trees and other ASTs modeled in object-oriented languages. Proebstin’s original BURS was meant to be an optimizing table-driven code generator converting an AST into a series of instructions, with every rule specifying a cost. The BURS implementation written as part of the LINQ to Everything toolkit further abstracts this by enabling table-driven cost optimizing translation across any pairs of languages modeled using generalized notions of trees, nodes, and tags. For example, a LINQ to SQL implementation starts off by converting .NET expression trees to an alternative tree representation that enables bottom-up tiling, followed by modeling the target SQL language using a similar tree object model. Finally, a set of cost-annotated rules is declared to translate between source and destination language (e.g. a MethodCallExpression to Queryable.Select can translate to a Project node in SQL, which is later turned into SELECT clause syntax). Use of BURS enabled the team to build a query processor relatively quickly.

クエリプロセッサを構築する際に遭遇したもう一つの障害は、IEnumerable<T>をベースにした同期LINQクエリ演算子と、データにアクセスするためにキー/バリューストアが提供する非同期APIとの間のインピーダンスミスマッチでした。これらの非同期APIはかなり煩雑で、当時の非同期プログラミングのための標準的な.NETパターン、すなわちAPM、EAP、Task<T>のどれにも合致していませんでした。その代わりに、非常に基本的なコールバックメカニズムを使用していましたが、これを翻訳するのは困難でした。このミスマッチを解決するために、BartはLINQ to Everythingのツールキットを拡張し、continuation-passing style (CPS)の書き換え機能を追加しました。これにより、BURSをCPSの書き換えフェーズと組み合わせることで、同期言語コンストラクトを非同期実行プランに簡単にマッピングできるようになりました。

One more stumbling block encountered while building the query processor was the impedance mismatch between the synchronous LINQ query operators based on IEnumerable<T> and the asynchronous APIs provided by the key/value store to access data. These asynchronous APIs were rather cumbersome and didn’t align with any of the standard .NET patterns for asynchronous programming at the time, i.e. the APM, EAP, or Task<T>. Instead, it used a pretty basic callback mechanism which was hard to translate to. In order to solve this mismatch, Bart extended the LINQ to Everything toolkit by adding continuation-passing style (CPS) rewriters, allowing for a straightforward mapping of synchronous language constructs to asynchronous execution plans by composing BURS with a CPS rewriting phase.

Reaqtorは、フロントエンドの問い合わせ言語（Rx演算子を使用したLINQ）と、実行時に使用するバックエンドの問い合わせ言語との間の翻訳を必要としないため、現在はBURSを使用していません。実際、Reaqtorが実際に「サービスとしてのRx」であることを考えると、ターゲット言語はソース言語と同型です。しかし、BURSは、将来的には、クエリの最適化を行うためにも有用です。BURSを、ITree<TFirst>で表現されたソース言語とITree<TSecond>で表現されたターゲット言語との間のテーブル駆動型のツリー変換として実装することで、同じ言語を記述するツリー間の変換を行うことも可能です。この時点で、BURSはトランスレーターではなくオプティマイザーとなります。BURSのアイデアは、後にReaqtorの一部として構築されたNuqleon.Linq.CompilerServices.Optimizersに組み込まれました。このライブラリは、代数的な恒等式の宣言的な指定を用いた木構造変換に基づいて、LINQスタイルの問い合わせ言語のオプティマイザを構築するための汎用フレームワークを提供します。BURSとの主な違いは、適用する最適化ルールのコストドリブンな順位付けがないことです。

Reaqtor doesn’t use BURS today because it doesn’t require a translation between a front-end query language (LINQ using Rx operators) and a back-end query language used for execution. In fact, the target language is isomorphic to the source language, given that Reaqtor is really “Rx as a service”. However, BURS can still prove useful in the future to perform query optimization. By implementing BURS as a table-driven tree transformation between a source language expressed as ITree<TFirst> and a target language expressed as ITree<TSecond>, it is also possible to perform transformations between trees describing the same language. At this point, BURS becomes an optimizer rather than a translator. Ideas of BURS were later incorporated in Nuqleon.Linq.CompilerServices.Optimizers which was built as part of Reaqtor. This library provides a general-purpose framework to build optimizers for LINQ-style query languages based on tree transformations using declarative specification of algebraic identities. The main difference compared to BURS is the lack of a cost-driven ranking of optimization rules to apply.